package com.emeraldparser.parse;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

import javax.swing.JFrame;
import javax.swing.JScrollPane;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.emeraldparser.symbol.Symbol;
import com.emeraldparser.symbol.SymbolClass;
import com.emeraldparser.symbol.SymbolClasses;
import com.emeraldparser.util.AbstractDeterministicAutomatonBuilder;
import com.emeraldparser.util.Automaton;
import com.emeraldparser.util.Automatons;
import com.emeraldparser.util.DeterministicAutomatonBuilder;
import com.emeraldparser.util.DirectedGraphEdge;
import com.emeraldparser.util.Graph.Edge;
import com.emeraldparser.util.Path;
import com.google.common.base.Function;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicate;
import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

/**
 * The base class for GLR parsers.
 * 
 * @author Adam Paynter
 *
 */
public abstract class AbstractParser {

	private static final Logger logger = LoggerFactory.getLogger(AbstractParser.class);

	private final Iterator<? extends Symbol<?>> symbolIterator;
	private final Deque<Symbol<?>> bufferedSymbols = new ArrayDeque<Symbol<?>>();
	protected final Automaton<Node, Symbol<?>> parseGraph = Automatons.create();
	private final Collection<Node> topNodes;
	private Deque<Reduction> queuedReductions = Lists.newLinkedList();
	private final Collection<Listener> listeners = Lists.newArrayListWithExpectedSize(1);
	protected final List<Node> orderedNodes = Lists.newLinkedList();
	protected final List<Symbol<?>> input = Lists.newLinkedList();

	private int currentIteration;
	private Node currentNode;

	public AbstractParser(Iterator<? extends Symbol<?>> symbolIterator) {
		this.symbolIterator = Preconditions.checkNotNull(symbolIterator, "Symbol iterator must not be null");
		this.topNodes = parseGraph.getAcceptVertices();
	}

	public void parse() {
		if (!true) {
		JFrame frame = new JFrame("Parser");
		frame.setVisible(true);
		frame.add(new JScrollPane(new ParseVisualizationPanel(this)));
		frame.setSize(800, 600);
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		}
		
		State startState = getStartState();
		currentIteration = 0;
		Node startNode = new Node(currentIteration, startState);
		
		parseGraph.addVertex(startNode);
		parseGraph.addStartVertex(startNode);
		orderedNodes.add(startNode);

		topNodes.add(startNode);
		
		Symbol<?> symbol;
		
		while ((symbol = readSymbol()) != null) {
			if (topNodes.isEmpty()) {
				throw new IllegalStateException("No top nodes");
			}
			
			fireUpdate();
			
			input.add(symbol);
			
			doReductions(symbol);
			doShifts(symbol);
			currentIteration++;
		}
		
		fireUpdate();

		doReductions(null);
		
		for (Node topNode : topNodes) {
			Collection<Symbol<?>> symbols = ImmutableList.copyOf(parseGraph.inboundEdgeLabels(topNode));
			logger.info("Final symbols: {}", symbols);
			for (Symbol<?> s : symbols) {
				prettyPrint(s, "");
			}
		}
		System.out.println(topNodes);
	}

	private void prettyPrint(Symbol<?> symbol, String indentation) {
		Object semanticValue = symbol.getSemanticValue();
		if (semanticValue instanceof Iterable<?>) {
			System.out.println(indentation + "- " + symbol.getSymbolClass());
			for (Iterator<?> i = ((Iterable<?>) semanticValue).iterator(); i.hasNext();) {
				Symbol<?> childSymbol = (Symbol<?>) i.next();
				prettyPrint(childSymbol, indentation + "  ");
			}
		} else if (semanticValue == null) {
			System.out.println(indentation + "- " + symbol.getSymbolClass());
		} else {
			System.out.println(indentation + "- " + semanticValue);
		}
	}

	private void fireUpdate() {
		for (Listener listener : listeners) {
			listener.update();
		}
	}

	private void doReductions(Symbol<?> symbol) {
		queuedReductions.clear();
		
		logger.debug("CURRENT INPUT SYMBOL: {}", symbol);
		logger.debug("*** REDUCTIONS ***");
		logger.debug("TOP: {}", topNodes);
		//logger.trace("GRAPH: {}", parseGraph);
		
		logger.trace("Queuing reductions on symbol {}...", symbol);
		
		for (Node node : topNodes) {
			currentNode = node;
			logger.trace("Queuing reductions on symbol {} in {}", symbol, node.state);
			node.queueReductions(symbol);
		}
		
		logger.trace("{} reductions queued", queuedReductions.size());
		
		while (!queuedReductions.isEmpty()) {
			Reduction reduction = queuedReductions.removeFirst();
			Rule rule = reduction.rule;
			
			Path<Node, Symbol<?>> path = reduction.path;
			
			List<Symbol<?>> rightHandSymbols = ImmutableList.copyOf(Lists.transform(
					Lists.newArrayList(path.edges()),
					new Function<Edge<Node, Symbol<?>>, Symbol<?>>() {
						@Override public Symbol<?> apply(Edge<Node, Symbol<?>> edge) {
							return edge.getLabel();
						}
					}
				));
			
			List<? extends Symbol<?>> leftHandSymbols = rule.reduce(rightHandSymbols);
			
			logger.trace("Reduced symbols {} using rule [{}], yielding {}...", new Object[]{ rightHandSymbols, reduction.rule, leftHandSymbols });
			
			if (leftHandSymbols.size() > 1) {
				throw new UnsupportedOperationException("Left hand sides greater than 1 in length");
			} else {
				Node leftSibling = reduction.path.getFirstVertex();
				try {
					for (Symbol<?> leftHandSymbol : leftHandSymbols) {
						State nextState = leftSibling.state.nextState(leftHandSymbol);
						
						Node rightSibling = null;
						for (Node topNode : topNodes) {
							if (topNode.state == nextState) {
								rightSibling = topNode;
							}
						}
						
						if (rightSibling != null) {
							if (!parseGraph.edges(leftSibling, rightSibling).isEmpty()) {
								// TODO Merge competing semantic values 
							} else {
								parseGraph.addDirectedEdge(leftSibling, rightSibling, leftHandSymbol);
								fireUpdate();
							}
						} else {
							rightSibling = new Node(currentIteration, nextState);
							parseGraph.addVertex(rightSibling);
							orderedNodes.add(rightSibling);
							topNodes.add(rightSibling);
							DirectedGraphEdge<Node, Symbol<?>> edge = DirectedGraphEdge.<Node, Symbol<?>>create(leftSibling, rightSibling, leftHandSymbol);
							parseGraph.addEdge(edge);
							fireUpdate();
							enqueueLimitedReductions(edge);
						}
						
						leftSibling = shiftState(leftSibling, leftHandSymbol, leftSibling.state.nextState(leftHandSymbol));
						// FIXME: This really has to be implemented according to the reduceViaPath subroutine found in the Elkhound paper.
						// We are missing further reductions that have been introduced because of this reduction.
					}
					
					topNodes.add(leftSibling);
				} catch (RuntimeException e) {
					// FIXME
					//e.printStackTrace();
				}
			}
			
			//shiftState(symbol, nextState);
		}
	}

	private void doShifts(Symbol<?> symbol) {
		logger.debug("*** SHIFTS ***");
		logger.debug("TOP: {}", topNodes);
		logger.debug("Shifting on symbol {}...", symbol);
		
		Collection<Node> oldTopNodes = clearTopNodes();
		if (symbol.getSymbolClass().equals(SymbolClasses.endOfInput())) {
			for (Node oldTopNode : oldTopNodes) {
				System.out.println(parseGraph.inboundEdgeLabels(oldTopNode));
			}
		}
		
		for (Node node : oldTopNodes) {
			currentNode = node;
			node.doShifts(symbol);
		}
	}

	private void enqueueLimitedReductions(final Edge<Node, Symbol<?>> edge) {
		Deque<Reduction> oldQueuedReductions = this.queuedReductions;
		Deque<Reduction> newQueuedReductions = Lists.newLinkedList();
		
		this.queuedReductions = newQueuedReductions;
		
		for (Node topNode : topNodes) {
			topNode.state.queueReductions(edge.getLabel());
		}
		
		Iterables.removeIf(
				queuedReductions,
				new Predicate<Reduction>() {
					@Override
					public boolean apply(Reduction reduction) {
						return !(reduction.path.containsEdge(edge) || reduction.path.size() == 0);
					}
				}
			);
		
		for (Reduction newQueuedReduction : newQueuedReductions) {
			logger.debug("Adding limited reduction: {}", newQueuedReduction);
		}
		
		oldQueuedReductions.addAll(newQueuedReductions);
		
		this.queuedReductions = oldQueuedReductions;
	}

	protected abstract State getStartState();

	protected void unreadSymbol(Symbol<?> symbol) {
		bufferedSymbols.addFirst(symbol);
	}

	protected String concatenateStrings(Iterable<? extends Symbol<?>> symbols) {
		StringBuilder stringBuilder = new StringBuilder();
		for (Symbol<?> symbol : symbols) {
			stringBuilder.append(toString(symbol.getSemanticValue()));
		}
		return stringBuilder.toString();
	}

	protected String toString(Object object) {
		if (object instanceof String) {
			return (String) object;
		} else if (object instanceof CharSequence) {
			return new StringBuilder().append( (CharSequence) object ).toString();
		} else if (object instanceof Iterable<?>) {
			Iterable<?> iterable = (Iterable<?>) object;
			StringBuilder stringBuilder = new StringBuilder();
			for (Object childObject : iterable) {
				stringBuilder.append(toString(childObject));
			}
			return stringBuilder.toString();
		} else if (object instanceof Symbol<?>) {
			Symbol<?> symbol = (Symbol<?>) object;
			return toString( symbol.getSemanticValue() );
		} else {
			return String.valueOf(object);
		}
	}

	/**
	 * 
	 * @param symbol
	 * @param nextState
	 */
	protected void shiftState(Symbol<?> symbol, State nextState) {
		shiftState(currentNode, symbol, nextState);
	}

	private Node shiftState(Node leftSibling, Symbol<?> symbol, State nextState) {
		Node rightSibling = null;
		
		logger.debug("Shifting on symbol {} from {} to {}", new Object[]{ symbol, leftSibling.state, nextState });
		
		for (Node node : topNodes) {
			if (node.state == nextState) {
				rightSibling = node;
				break;
			}
		}
		
		if (rightSibling == null) {
			rightSibling = new Node(currentIteration + 1, nextState);
			parseGraph.addVertex(rightSibling);
			orderedNodes.add(rightSibling);
			topNodes.add(rightSibling);
		}
		
		parseGraph.addDirectedEdge(leftSibling, rightSibling, symbol);
		fireUpdate();
		
		return rightSibling;
	}

	protected void queueReductions(Rule rule) {
		SymbolClass rightHandSide = rule.getRightHandSide();
		final Automaton<? extends SymbolClass.State, ? extends SymbolClass> automaton = rightHandSide.toAutomaton();
		
		// TODO Traverse the parse graph backwards from the top nodes.
		
		for (Node node : topNodes) {
			//if (node.iteration == 14) {
			if (rule.toString().equals("((('a'..'z') | \"_\")*) = (('a'..'z') | \"_\")*")) {
				System.out.print("");
			}
			
			final Set<Object> pseudoState = Sets.newHashSet();
			pseudoState.add(node);
			pseudoState.addAll(automaton.getAcceptVertices());
			
			
			Automaton<ImmutableSet<Object>, Symbol<?>> aaa = new AbstractDeterministicAutomatonBuilder<Object, Symbol<?>>() {

				@Override
				protected boolean isAcceptClosure(ImmutableSet<Object> closure) {
					// TODO Auto-generated method stub
					for (Object vertex : closure) {
						if (automaton.getStartVertices().contains(vertex)) {
							return true;
						}
					}
					return false;
				}

				@Override
				protected Iterable<? extends Object> getStartVertices() {
					// TODO Auto-generated method stub
					return pseudoState;
				}

				@Override
				protected Iterable<? extends Object> getPeers(Object vertex) {
					// TODO Auto-generated method stub
					if (vertex instanceof SymbolClass.State) {
						Set<Object> peers = Sets.newHashSet();
						peers.addAll( ((Automaton) automaton).predecessors((SymbolClass.State) vertex, null) );
						peers.addAll( ((Automaton) automaton).successors((SymbolClass.State) vertex, null) );
						return peers;
					} else {
						return ImmutableList.of();
					}
				}

				@Override
				protected Iterable<? extends Symbol<?>> getOutboundEdgeLabels(Iterable<? extends Object> closure) {
					// TODO Auto-generated method stub
					Set<SymbolClass> symbolClasses = Sets.newHashSet();
					
					Automaton a = automaton;
					
					for (Object vertex : closure) {
						if (vertex instanceof SymbolClass.State) {
							symbolClasses.addAll(a.inboundEdgeLabels((SymbolClass.State) vertex));
						}
					}
					
					Set<Symbol<?>> symbols = Sets.newHashSet();
					
					for (Object vertex : closure) {
						if (vertex instanceof Node) {
							Node node = (Node) vertex;
							for (Symbol<?> symbol : parseGraph.inboundEdgeLabels(node)) {
								if (symbolClasses.contains(symbol.getSymbolClass())) {
									symbols.add(symbol);
								}
							}
						}
					}
					
					return symbols;
				}

				@Override
				protected Iterable<? extends Object> getSuccessors(Object vertex, Symbol<?> edgeLabel) {
					// TODO Auto-generated method stub
					if (vertex instanceof SymbolClass.State) {
						Automaton a = automaton;
						return a.predecessors(vertex, edgeLabel.getSymbolClass());
					}
					
					if (vertex instanceof Node) {
						return parseGraph.predecessors((Node) vertex, edgeLabel);
					}
					
					return ImmutableList.of();
				}
				
			}.buildDeterministicAutomaton();
			
			Automaton<ImmutableSet<Object>, Symbol<?>> det = Automatons.invert(aaa);
			
			Collection<Path<ImmutableSet<Object>, Symbol<?>>> paths = Automatons.findPaths(det);
			
			for (Path<ImmutableSet<Object>, Symbol<?>> path : paths) {
				// FIXME Will this work?
				
				path.getFirstVertex();
				
				for (Path<Node, Symbol<?>> ppp : allPaths(path)) {
					logger.debug("Possible reduction: {}", ppp);
					queuedReductions.add(new Reduction(rule, ppp));
				}
				
				/*
				Path<Node, Symbol<?>> realPath = new Path<Node, Symbol<?>>( onlyNode(path.getFirstVertex()) );
				
				for (Edge<ImmutableSet<Object>, Symbol<?>> e : path.edges()) {
					realPath = realPath.appendEdge((Edge) DirectedGraphEdge.create(onlyNode(e.getSource()), onlyNode(e.getDestination()), e.getLabel()));
				}
				
				queuedReductions.add(new Reduction(rule, realPath));
				*/
			}
			
			//System.out.println(paths);
			
			//System.out.println(det);
		}
		
		//queueReductionsFrom(rule, rule.getStartStates());
	}

	private Collection<Path<Node, Symbol<?>>> allPaths(Path<ImmutableSet<Object>, Symbol<?>> path) {
		Collection<Path<Node, Symbol<?>>> allPaths = Sets.newHashSet();
		
		if (path.size() == 0) {
			for (Node newFirstNode : nodes(path.getFirstVertex())) {
				allPaths.add(Path.<Node, Symbol<?>>create(newFirstNode));
			}
		} else {
			Edge<ImmutableSet<Object>, Symbol<?>> firstEdge = path.edges().iterator().next();
			for (Node newFirstNode : nodes(path.getFirstVertex())) {
				for (Path<Node, Symbol<?>> subRealPath : allPaths(path.from(1))) {
					List<Edge<Node, Symbol<?>>> eee = Lists.newArrayListWithCapacity(path.size());
					eee.add((Edge) DirectedGraphEdge.create(newFirstNode, subRealPath.getFirstVertex(), firstEdge.getLabel()));
					eee.addAll(subRealPath.edges());
					
					//Path<Node, Symbol<?>> newThing = new Path<Node, Symbol<?>>(newFirstNode).appendPath(subRealPath);
					//allPaths.add();
					allPaths.add(Path.<Node, Symbol<?>>create(newFirstNode, eee));
				}
			}
		}
		
		return allPaths;
	}

	private Collection<Node> nodes(Iterable<? extends Object> objects) {
		Set<Node> nodes = Sets.newHashSet();
		
		for (Object object : objects) {
			if (object instanceof Node) {
				nodes.add( (Node) object );
			}
		}
		
		return nodes;
	}

	private Node onlyNode(Iterable<? extends Object> objects) {
		return Iterables.getOnlyElement(nodes(objects));
	}

	/**
	 * Called by subclasses to queue all reductions on paths beginning at startState.
	 * 
	 * @param rule
	 * @param startState
	 */
	protected void queueReductionsFrom(Rule rule, State startState) {
		queueReductionsFrom(rule, ImmutableSet.of(startState));
	}

	protected void queueReductionsFrom(Rule rule, Collection<? extends State> startStates) {
		logger.trace("Queueing reductions from {}", startStates);
		queuedReductions.addAll(reductionsFrom(startStates, rule));
	}

	private Collection<Node> clearTopNodes() {
		Collection<Node> oldTopNodes = new ArrayList<Node>(topNodes);
		topNodes.clear();
		return oldTopNodes;
	}

	private Symbol<?> readSymbol() {
		if (bufferedSymbols.isEmpty()) {
			try {
				return symbolIterator.next();
			} catch (NoSuchElementException e) {
				return null; // TODO is this the best way to handle the end of input?
			}
		} else {
			return bufferedSymbols.removeFirst();
		}
	}

	private Collection<Reduction> reductionsFrom(Collection<? extends State> startStates, Rule rule) {
		Collection<Reduction> reductions = Lists.newArrayListWithExpectedSize(1);
		
		for (Node node : topNodes) {
			for (Path<Node, Symbol<?>> path : pathsFrom(startStates, node)) {
				reductions.add(new Reduction(rule, path));
			}
		}
		
		return reductions;
	}

	private Collection<Path<Node, Symbol<?>>> pathsFrom(Collection<? extends State> startStates, Node currentNode) {
		Collection<Path<Node, Symbol<?>>> paths = Lists.newArrayListWithExpectedSize(1);
		
		if (startStates.contains(currentNode.state)) {
			paths.add(Path.<Node, Symbol<?>>create(currentNode));
		} else {
			for (Edge<Node, Symbol<?>> leftLink : parseGraph.inboundEdges(currentNode)) {
				for (Path<Node, Symbol<?>> leftPath : pathsFrom(startStates, leftLink.getSource())) {
					paths.add(leftPath.appendEdge(leftLink));
				}
			}
		}
		
		return paths;
	}

	protected class Node {

		protected final int iteration;
		protected final State state;
		private final transient int hashCode;

		private Node(int iteration, State state) {
			this.iteration = iteration;
			this.state = state;
			this.hashCode = Objects.hashCode(iteration, state);
		}

		private void queueReductions(Symbol<?> symbol) {
			state.queueReductions(symbol);
		}

		private void doShifts(Symbol<?> symbol) {
			state.doShifts(symbol);
		}

		@Override
		public String toString() {
			return String.valueOf(state) + "@" + iteration;
		}

		@Override
		public int hashCode() {
			return hashCode;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			
			if (obj == null) {
				return false;
			}
			
			if (getClass() != obj.getClass()) {
				return false;
			}
			
			Node other = (Node) obj;
			
			if (!getParser().equals(other.getParser())) {
				return false;
			}
			
			return iteration == other.iteration
			    && Objects.equal(state, other.state);
		}

		private AbstractParser getParser() {
			return AbstractParser.this;
		}
	
	}

	private static class Reduction {
		
		private final Rule rule;
		private final Path<Node, Symbol<?>> path;
		
		public Reduction(Rule rule, Path<Node, Symbol<?>> path) {
			this.rule = rule;
			this.path = path;
		}
		
		@Override
		public String toString() {
			return "Reduction[rule: " + rule + ", path: " + path + "]";
		}
		
	}

	protected static interface Listener {
		
		public void update();
		
	}

	protected void addListener(Listener listener) {
		listeners.add(listener);
	}

}
